package com.ls.tree;

import lombok.Data;

/**
 * 二叉树的前中后遍历
 */
@Data
public class BinaryTree {

    private Node root;

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node3.setRight(node7);

//        binaryTree.preOrder();  // 前序 1245367
//        binaryTree.midOrder(); // 中序 4251637
//        binaryTree.postOrder(); // 后序4526731
//        System.out.println(binaryTree.preSearch(1));
//        System.out.println(binaryTree.midSearch(1));
        System.out.println(binaryTree.postSearch(5));
    }


    public void preOrder(){
        if (this.root != null){
            this.root.preOrder();
        }
    }

    public void midOrder(){
        if (this.root != null){
            this.root.midOrder();
        }
    }
    public void postOrder(){
        if (this.root != null){
            this.root.postOrder();
        }
    }

    public Integer preSearch(int target){
        if (root != null){
            return root.preSearch(target);
        }
        return null;
    }

    public Integer midSearch(int target){
        if (root != null){
            return root.midSearch(target);
        }
        return null;
    }

    public Integer postSearch(int target){
        if (root != null){
            return root.postSearch(target);
        }
        return null;
    }

    @Data
    static class Node{
        Integer data; // 数据用int存储
        private Node left;
        private Node right;

        public Node(Integer data) {
            this.data = data;
        }

        /**
         * 前序遍历 DLR
         */
        public void preOrder(){
            System.out.print(this.data);
            if (this.left != null){
                this.left.preOrder();
            }
            if (this.right != null){
                this.right.preOrder();
            }
        }


        /** LDR
         * 中序遍历
         */
        public void midOrder() {
            if (this.left != null){
                this.left.midOrder();
            }
            System.out.print(this.data);
            if (this.right != null){
                this.right.midOrder();
            }
        }


        /** LRD
         * 后序遍历
         */
        public void postOrder(){
            if (this.left != null){
                this.left.postOrder();
            }
            if (this.right != null){
                this.right.postOrder();
            }

            System.out.print(this.data);

        }

        /**
         * 前序搜索
         * @param target
         * @return
         */
        public Integer preSearch(Integer target){
            if (this.data.equals(target)){
                return this.data;
            }
            Integer result = null;
            if (this.left != null){
                 result = this.left.preSearch(target);
            }
            if (result !=null){
                return result;
            }
            if (this.right != null){
                return this.right.preSearch(target);
            }
            return result;
        }


        /**
         * 中序搜索
         * @param target
         * @return
         */
        public Integer midSearch(Integer target){
            Integer result = null;
            if (this.left != null){
                result = this.left.preSearch(target);
            }
            // 判断在左边的字数是否找到是否
            if (result !=null){
                return result;
            }
            if (this.data.equals(target)){
                return this.data;
            }
            if (this.right != null){
                return this.right.preSearch(target);
            }
            return result;
        }

        /**
         * 后序搜索
         * @param target
         * @return
         */
        public Integer postSearch(Integer target){
            Integer result = null;
            if (this.left != null){
                result = this.left.postSearch(target);
            }
            if (result !=null){
                return result;
            }
            if (this.right != null){
                result = this.right.postSearch(target);
            }
            // 判断在左边的字数是否找到是否
            if (result !=null){
                return result;
            }
            if (this.data.equals(target)){
                return this.data;
            }
            return result;
        }




    }
}
